package sort;

import java.util.Arrays;


/**
 * 插入排序，类似于一张张拿扑克牌，拿到后放在最右边，然后向前交换
 * O(n^2)
 * 稳定：和冒泡一样，碰到相等的牌就不向前移到了
 *
 * @author Liaorun
 */
public class InsertionSort {

    public static void main(String[] args) {

    }


    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        for (int i = 1; i < arr.length; i++) {
            // 0 ~ i 做到有序
            // 向前比较，前面的比自己大就交换
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }

    /**
     * 交换一个数组中的元素
     * i != j,否则数据arr[i] = 0
     *
     * @param arr 数组
     * @param j   一个下标
     * @param i   一个下标
     */
    private static void swap(int[] arr, int j, int i) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }


}
